{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Longest Uncommon Subsequence II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #two-pointers #string #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #双指针 #字符串 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findLUSlength"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最长特殊序列 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定字符串列表&nbsp;<code>strs</code> ，返回其中 <strong>最长的特殊序列</strong>&nbsp;的长度。如果最长特殊序列不存在，返回 <code>-1</code> 。</p>\n",
    "\n",
    "<p><strong>特殊序列</strong> 定义如下：该序列为某字符串 <strong>独有的子序列（即不能是其他字符串的子序列）</strong>。</p>\n",
    "\n",
    "<p>&nbsp;<code>s</code>&nbsp;的&nbsp;<strong>子序列</strong>可以通过删去字符串&nbsp;<code>s</code>&nbsp;中的某些字符实现。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，<code>\"abc\"</code>&nbsp;是 <code>\"aebdc\"</code>&nbsp;的子序列，因为您可以删除<code>\"a<u>e</u>b<u>d</u>c\"</code>中的下划线字符来得到 <code>\"abc\"</code>&nbsp;。<code>\"aebdc\"</code>的子序列还包括<code>\"aebdc\"</code>、 <code>\"aeb\"</code>&nbsp;和 <font color=\"#c7254e\" face=\"Menlo, Monaco, Consolas, Courier New, monospace\"><span style=\"font-size: 12.6px; background-color: rgb(249, 242, 244);\">\"\"</span></font>&nbsp;(空字符串)。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> strs = [\"aba\",\"cdc\",\"eae\"]\n",
    "<strong>输出:</strong> 3\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> strs = [\"aaa\",\"aaa\",\"aa\"]\n",
    "<strong>输出:</strong> -1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= strs.length &lt;= 50</code></li>\n",
    "\t<li><code>1 &lt;= strs[i].length &lt;= 10</code></li>\n",
    "\t<li><code>strs[i]</code>&nbsp;只包含小写英文字母</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [longest-uncommon-subsequence-ii](https://leetcode.cn/problems/longest-uncommon-subsequence-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [longest-uncommon-subsequence-ii](https://leetcode.cn/problems/longest-uncommon-subsequence-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"aba\",\"cdc\",\"eae\"]', '[\"aaa\",\"aaa\",\"aa\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, a: str, b: str) -> int:\n",
    "        return -1 if a == b else max(len(a), len(b))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, a: str, b: str) -> int:\n",
    "        return max(len(a), len(b)) if a!=b else -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, a: str, b: str) -> int:\n",
    "        if a == b:\n",
    "            return -1\n",
    "        return max(len(a), len(b))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, a: str, b: str) -> int:\n",
    "        ans = -1\n",
    "        temp=[]\n",
    "        temp2=[]\n",
    "        for i in range(len(a)):\n",
    "            for j in range(i+1,len(a)+1):\n",
    "                tmp = a[i:j]\n",
    "                temp.append(tmp)\n",
    "        for i in range(len(b)):\n",
    "            for j in range(i + 1, len(b) + 1):\n",
    "                tmp = b[i:j]\n",
    "                temp2.append(tmp)\n",
    "        temp.sort(key=len,reverse=True)\n",
    "        temp2.sort(key=len,reverse=True)\n",
    "        for i in temp:\n",
    "            if i not in b:\n",
    "                ans = max(ans,len(i))\n",
    "        for j in temp2:\n",
    "            if j not in a:\n",
    "                ans = max(ans,len(j))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, a: str, b: str) -> int:\n",
    "        return max(len(a), len(b)) if a != b else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, a: str, b: str) -> int:\n",
    "        if a.find(b)>=0 and b.find(a)>=0:\n",
    "            return -1\n",
    "        else:\n",
    "            return max(len(a),len(b))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, a: str, b: str) -> int:\n",
    "        if a in b and b in a:\n",
    "            return -1\n",
    "        else:\n",
    "            return max(len(a), len(b))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, a: str, b: str) -> int:\n",
    "        \n",
    "        if a == b:\n",
    "            return -1\n",
    "        \n",
    "        return max(len(a), len(b))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, a: str, b: str) -> int:\n",
    "        \n",
    "        if a == b:\n",
    "            return -1\n",
    "        else:\n",
    "            return max(len(a), len(b))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, a: str, b: str) -> int:\n",
    "        if a==b:\n",
    "            return -1\n",
    "        return max(len(a),len(b))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, a: str, b: str) -> int:\n",
    "        # 如果两个字符串的内容相同，返回-1\n",
    "        # 如果长度不同，返回长的长度\n",
    "        return -1 if a==b else max(len(a), len(b))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, a: str, b: str) -> int:\n",
    "        return -1 if a==b else max(len(a), len(b))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, a: str, b: str) -> int:\n",
    "        return -1 if a==b else max(len(a),len(b))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, a: str, b: str) -> int:\n",
    "        len_a, len_b = len(a), len(b)\n",
    "        if len_a != len_b:\n",
    "            return max(len_a, len_b)\n",
    "        i = 0\n",
    "        for c_b in b:\n",
    "            while i < len_a and c_b != a[i]:\n",
    "                i += 1\n",
    "            if i == len_a:\n",
    "                return len_a\n",
    "            i += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, a: str, b: str) -> int:\n",
    "        # 不能是其他字符串的子序列\n",
    "        return max(len(a),len(b)) if a != b else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def findLUSlength(self, a, b):\n",
    "        if a==b:\n",
    "            return -1\n",
    "        else:\n",
    "            return max(len(a),len(b))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, a: str, b: str) -> int:\n",
    "        return -1 if a == b else max(len(a), len(b))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, a: str, b: str) -> int:\n",
    "        return -1 if a == b else max(len(a),len(b))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, a: str, b: str) -> int:\n",
    "        \n",
    "        if a == b:\n",
    "            return -1\n",
    "        else:\n",
    "            return max(len(a), len(b))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, a: str, b: str) -> int:\n",
    "        return -1 if a == b else max(len(a), len(b))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, a: str, b: str) -> int:\n",
    "        return max(len(a), len(b)) if a != b else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, a: str, b: str) -> int:\n",
    "        if a != b:\n",
    "            return max(len(a),len(b))\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, a: str, b: str) -> int:\n",
    "        return max(len(a), len(b)) if a != b else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, a: str, b: str) -> int:\n",
    "        return -1 if a == b else max(len(a), len(b))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, a: str, b: str) -> int:\n",
    "        return max(len(a), len(b)) if a != b else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, a: str, b: str) -> int:\n",
    "        \n",
    "        if len(a) < len(b):\n",
    "            return len(b)\n",
    "        elif len(a) > len(b):\n",
    "            return len(a)\n",
    "        else:\n",
    "            if a == b:\n",
    "                return -1\n",
    "            else:\n",
    "                return len(a)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, a: str, b: str) -> int:\n",
    "        n1 = len(a)\n",
    "        n2 = len(b)\n",
    "        if n1!=n2:\n",
    "            return max(n1, n2)\n",
    "        else:\n",
    "            if a == b:\n",
    "                return -1\n",
    "            else:\n",
    "                return n1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, a: str, b: str) -> int:\n",
    "        m = len(a)\n",
    "        n = len(b)\n",
    "        j=0\n",
    "        if m != n: return max(m,n)\n",
    "        for i in range(m):\n",
    "            if a[i] == b[j]:\n",
    "                j += 1\n",
    "        if j == m:\n",
    "            return -1\n",
    "        else:\n",
    "            return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # def findLUSlength(self, a: str, b: str) -> int:\n",
    "    #     # 这道题的意思是说只有a or b是另外一个的\"子串\"时才有效，否则就不是\n",
    "    #     # 双指针\n",
    "    #     if (len(a) < len(b)):\n",
    "    #         a1, b1 = b, a\n",
    "    #     else:\n",
    "    #         a1, b1 = a, b\n",
    "    #     x = len(a1)\n",
    "    #     y = len(b1)\n",
    "    #     i = 0\n",
    "    #     j = 0\n",
    "    #     cnt = 0\n",
    "    #     while (i < x and j < y):\n",
    "    #         if (a1[i] == b1[j]):\n",
    "    #             i += 1\n",
    "    #             j += 1\n",
    "    #             cnt += 1\n",
    "    #         else:\n",
    "    #             i += 1\n",
    "    #     if (cnt == y):\n",
    "    #         return x - y if x > y else -1\n",
    "    #     else:\n",
    "    #         return x\n",
    "    def findLUSlength(self, a: str, b: str) -> int:\n",
    "        if (len(a) != len(b)):\n",
    "            return len(a) if len(a) > len(b) else len(b)\n",
    "        for i in range(len(a)):\n",
    "            if (a[i] != b[i]):\n",
    "                return len(a)\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, a: str, b: str) -> int:\n",
    "        return max(len(a),len(b)) if a!=b else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, a: str, b: str) -> int:\n",
    "        if len(a)!=len(b):\n",
    "            return max(len(a),len(b))\n",
    "        i=0\n",
    "        while i<len(a) and a[i]==b[i]:\n",
    "            i+=1\n",
    "        if i==len(a):\n",
    "            return -1\n",
    "        return len(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, a: str, b: str) -> int:\n",
    "        m = len(a)\n",
    "        n = len(b)\n",
    "        return max(m,n) if a !=b else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, a: str, b: str) -> int:\n",
    "      m,n=len(a),len(b)\n",
    "      return max(m,n) if a!=b else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, a: str, b: str) -> int:\n",
    "        # 如果两个字符串的内容相同，返回-1\n",
    "        # 如果长度不同，返回长的长度\n",
    "        return -1 if a==b else max(len(a), len(b))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, a: str, b: str) -> int:\n",
    "        if a==b:\n",
    "            return -1\n",
    "        else:\n",
    "            return max(len(a),len(b))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, a: str, b: str) -> int:\n",
    "        \n",
    "        if len(a) < len(b):\n",
    "            return len(b)\n",
    "        elif len(a) > len(b):\n",
    "            return len(a)\n",
    "        else:\n",
    "            if a == b:\n",
    "                return -1\n",
    "            else:\n",
    "                return len(a)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, a: str, b: str) -> int:\n",
    "        # if a != b:\n",
    "        #     return max(len(a),len(b))\n",
    "        # else:\n",
    "        #     return -1\n",
    "\n",
    "        # sa = []\n",
    "        # sb = []\n",
    "        # for i in range(len(a)):\n",
    "        #     if a[i] not in b:\n",
    "        #         sa.append(a[i])\n",
    "        #         i+=1\n",
    "        # for j in range(len(b)):\n",
    "        #     if b[j] not in a:\n",
    "        #         sb.append(b[j])\n",
    "        #         j+=1           \n",
    "        # if (len(sa)+len(sb)) != 0:\n",
    "        #     return max(len(sa),len(sb))\n",
    "        # else:\n",
    "        #     return -1\n",
    "        return (max(len(a),len(b)) if a != b else -1)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, a: str, b: str) -> int:\n",
    "        if a==b:\n",
    "            return -1\n",
    "        if len(a)<len(b):\n",
    "            return len(b)\n",
    "        else:\n",
    "            return len(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, a: str, b: str) -> int:\n",
    "        la, lb = len(a), len(b)\n",
    "        if la != lb:\n",
    "            return max(la, lb)\n",
    "        elif a == b:\n",
    "            return -1\n",
    "        else:\n",
    "            return la\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, a: str, b: str) -> int:\n",
    "        if a==b:\n",
    "            return -1\n",
    "        return max(len(a),len(b))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, a: str, b: str) -> int:\n",
    "        return max(len(a),len(b)) if a!=b else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, a: str, b: str) -> int:\n",
    "        if a == b:\n",
    "            return -1\n",
    "        return max(len(a), len(b))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, a: str, b: str) -> int:\n",
    "        if a==b:\n",
    "            return -1\n",
    "        else:\n",
    "            return max(len(a),len(b))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, a: str, b: str) -> int:\n",
    "        return max(len(a), len(b)) if a != b else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, a: str, b: str) -> int:\n",
    "        return max(len(a), len(b)) if a != b else -1\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, a: str, b: str) -> int:\n",
    "        return max(len(a), len(b)) if a != b else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, a: str, b: str) -> int:\n",
    "        if a == b:\n",
    "            return -1\n",
    "        else:\n",
    "            return max(len(a), len(b))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def findLUSlength(self, a: str, b: str) -> int:\r\n",
    "        return -1 if a==b else max(len(a), len(b))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, a: str, b: str) -> int:\n",
    "        if a == b:\n",
    "            return -1\n",
    "        return max(len(a), len(b))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, a: str, b: str) -> int:\n",
    "        return -1 if a == b else max(len(a),len(b))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, a: str, b: str) -> int:\n",
    "        if a != b:\n",
    "            return max(len(a), len(b))\n",
    "        else: return -1\n",
    "            \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, a: str, b: str) -> int:\n",
    "        \n",
    "        if a == b:\n",
    "            return -1\n",
    "        else:\n",
    "            return max(len(a), len(b))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, a: str, b: str) -> int:\n",
    "        if a != b:\n",
    "            return max(len(a),len(b))\n",
    "        else:\n",
    "            return -1\n",
    "\n",
    "        # sa = []\n",
    "        # sb = []\n",
    "        # for i in range(len(a)):\n",
    "        #     if a[i] not in b:\n",
    "        #         sa.append(a[i])\n",
    "        #         i+=1\n",
    "        # for j in range(len(b)):\n",
    "        #     if b[j] not in a:\n",
    "        #         sb.append(b[j])\n",
    "        #         j+=1           \n",
    "        # if (len(sa)+len(sb)) != 0:\n",
    "        #     return max(len(sa),len(sb))\n",
    "        # else:\n",
    "        #     return -1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, a: str, b: str) -> int:\n",
    "        return -1 if a == b else max(len(a),len(b)) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, a: str, b: str) -> int:\n",
    "        return max(len(a),len(b)) if a!=b else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, a: str, b: str) -> int:\n",
    "        if a == b: return -1\n",
    "        if len(a) != len(b): return max(len(a), len(b))\n",
    "        return len(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, a: str, b: str) -> int:\n",
    "        \n",
    "        if a == b:\n",
    "            return -1\n",
    "        else:\n",
    "            return max(len(a), len(b))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, a: str, b: str) -> int:\n",
    "        return max(len(a), len(b)) if a != b else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, a: str, b: str) -> int:\n",
    "        # m,n=len(a),len(b)\n",
    "        if len(a)!=len(b):\n",
    "            return max(len(a),len(b))\n",
    "        else:\n",
    "            return -1 if a==b else len(b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, a: str, b: str) -> int:\n",
    "        if a==b:\n",
    "            return -1\n",
    "        # if len(set(a))==len(set(b)):\n",
    "        return max(len(a),len(b))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, a: str, b: str) -> int:\n",
    "        return -1 if a == b else max(len(a), len(b))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, a: str, b: str) -> int:\n",
    "        # list_a = sorted(list(a))\n",
    "        # list_b = sorted(list(b))\n",
    "        # substring_a = []\n",
    "        # substring_b = []\n",
    "\n",
    "        # i = 0\n",
    "        # j = 0\n",
    "\n",
    "        # while(1):\n",
    "        #     if (i == len(list_a)) or (j == len(list_b)):\n",
    "        #         break\n",
    "        #     if list_a[i] == list_b[j]:\n",
    "        #         i += 1\n",
    "        #         j += 1\n",
    "        #         continue\n",
    "            \n",
    "        #     if list_a[i] < list_b[j]:\n",
    "        #         substring_a.append(list_a[i])\n",
    "        #         i += 1\n",
    "        #     elif list_a[i] > list_b[j]:\n",
    "        #         substring_b.append(list_b[j])\n",
    "        #         j += 1\n",
    "        \n",
    "        # if (i == len(list_a)):\n",
    "        #     while (j < len(list_b)):\n",
    "        #         substring_b.append(list_b[j])\n",
    "        #         j += 1\n",
    "\n",
    "        # if (j == len(list_b)):\n",
    "        #     while (i < len(list_a)):\n",
    "        #         substring_a.append(list_a[i]) \n",
    "        #         i += 1\n",
    "\n",
    "        # if (len(substring_a) == 0 and len(substring_b) == 0):\n",
    "        #     return -1\n",
    "\n",
    "        # return len(substring_a) if len(substring_b) < len(substring_a) else len(substring_b)\n",
    "        return max(len(a), len(b)) if a != b else -1\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, a: str, b: str) -> int:\n",
    "        return max(len(a), len(b)) if a != b else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, a: str, b: str) -> int:\n",
    "        return -1 if a == b else max(len(a), len(b))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, a: str, b: str) -> int:\n",
    "        return -1 if a == b else max(len(a), len(b))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, a: str, b: str) -> int:\n",
    "        return -1 if a==b else max(len(a), len(b))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, strs: List[str]) -> int:\n",
    "        def is_subseq(s: str, t: str) -> bool:\n",
    "            pt_s = pt_t = 0\n",
    "            while pt_s < len(s) and pt_t < len(t):\n",
    "                if s[pt_s] == t[pt_t]:\n",
    "                    pt_s += 1\n",
    "                pt_t += 1\n",
    "            return pt_s == len(s)\n",
    "        \n",
    "        ans = -1\n",
    "        for i, s in enumerate(strs):\n",
    "            check = True\n",
    "            for j, t in enumerate(strs):\n",
    "                if i != j and is_subseq(s, t):\n",
    "                    check = False\n",
    "                    break\n",
    "            if check:\n",
    "                ans = max(ans, len(s))\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, strs: List[str]) -> int:\n",
    "        def is_son(m, n):\n",
    "            p = 0\n",
    "            for i in range(len(n)):\n",
    "                if m[p] == n[i]:\n",
    "                    p += 1\n",
    "                if p == len(m):\n",
    "                    return True\n",
    "            return False\n",
    "        n = len(strs)\n",
    "        ans = -1\n",
    "        for i in range(n):\n",
    "            cur = len(strs[i])\n",
    "            for j in range(n):\n",
    "                if j == i:\n",
    "                    continue\n",
    "                if is_son(strs[i], strs[j]):\n",
    "                    cur = -1\n",
    "            ans = max(ans, cur)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, strs: List[str]) -> int:\n",
    "        ans = -1\n",
    "        def is_sub(s, t):\n",
    "            pt_s = pt_t = 0\n",
    "            while pt_s < len(s) and pt_t < len(t):\n",
    "                if s[pt_s] == t[pt_t]:\n",
    "                    pt_s += 1\n",
    "                pt_t += 1\n",
    "            return pt_s == len(s)\n",
    "        for i, s in enumerate(strs):\n",
    "            if len(s) <= ans:\n",
    "                continue\n",
    "            check = True\n",
    "            for j, t in enumerate(strs):\n",
    "                if i != j and is_sub(s, t):\n",
    "                    check = False\n",
    "                    break\n",
    "            if check:\n",
    "                ans = max(ans, len(s))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, strs: List[str]) -> int:\n",
    "        #找数组中，最长的孤儿。\n",
    "        def isSub(s,t):\n",
    "            pt_s=pt_t=0\n",
    "            while pt_s<len(s) and pt_t<len(t):\n",
    "                if s[pt_s]==t[pt_t]:\n",
    "                    pt_s+=1\n",
    "                    pt_t+=1\n",
    "                else:\n",
    "                    pt_t+=1\n",
    "            return pt_s==len(s)\n",
    "        \n",
    "        ans=-1\n",
    "        for i,s in enumerate(strs):\n",
    "            check=True\n",
    "            for j,t in enumerate(strs):\n",
    "                if i!=j and isSub(s,t):\n",
    "                    check=False#判断s是不是t的子串\n",
    "                    break\n",
    "            if check:\n",
    "                ans=max(ans,len(s))\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, strs: List[str]) -> int:\n",
    "        def is_subseq(s1,s2):\n",
    "            i,j=0,0\n",
    "            while i<len(s1) and j <len(s2):\n",
    "                if s1[i]==s2[j]:\n",
    "                    i+=1\n",
    "                j+=1\n",
    "            return i==len(s1)\n",
    "        res=-1\n",
    "        for i, s1 in enumerate(strs):\n",
    "            t = True\n",
    "            for j, s2 in enumerate(strs):\n",
    "                if i != j and is_subseq(s1, s2):\n",
    "                    t = False\n",
    "                    break\n",
    "            if t:\n",
    "                res = max(res, len(s1))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, strs: List[str]) -> int:\n",
    "        def is_subseq(s: str, t: str) -> bool:\n",
    "            pt_s = pt_t = 0\n",
    "            while pt_s < len(s) and pt_t < len(t):\n",
    "                if s[pt_s] == t[pt_t]:\n",
    "                    pt_s += 1\n",
    "                pt_t += 1\n",
    "            return pt_s == len(s)\n",
    "\n",
    "        ans = -1\n",
    "        for i, s in enumerate(strs):\n",
    "            check = True\n",
    "            for j, t in enumerate(strs):\n",
    "                if i != j and is_subseq(s, t):\n",
    "                    check = False\n",
    "                    break\n",
    "            if check:\n",
    "                ans = max(ans, len(s))\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, strs) -> int:        \n",
    "        '''\n",
    "        10/24 review\n",
    "        求最长的特殊序列，首先从最长的序列开始，判断strs中是否存在它的子序列，如果没有，则为最长长度\n",
    "        具体\"判断strs中是否存在它的子序列\",长度小于它的序列一定不是它的母序列\n",
    "        '''\n",
    "        strs = sorted(strs, key=len ,reverse=True)\n",
    "        for i in range(len(strs)):\n",
    "            if not self.isSubstrofAnother(strs,i):\n",
    "                return len(strs[i])\n",
    "        return -1 \n",
    "    \n",
    "    def isSubstrofAnother(self,strs,idx):\n",
    "        for i in range(len(strs)):              # 已经按照长度降序排列\n",
    "            if i == idx:\n",
    "                continue\n",
    "            elif len(strs[i]) < len(strs[idx]):\n",
    "                break\n",
    "            else:\n",
    "                if self.isSubstr(strs[i], strs[idx]):\n",
    "                    return True\n",
    "        return False\n",
    "    \n",
    "    def isSubstr(self, s, t):\n",
    "        N, n = len(s), len(t)\n",
    "        cnt, j = 0, 0\n",
    "        for i in range(N):\n",
    "            if j < n:\n",
    "                if s[i] == t[j]:\n",
    "                    cnt += 1\n",
    "                    j += 1\n",
    "            else:\n",
    "                break\n",
    "        return cnt == n\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    strs = [\"aba\",\"cdc\",\"eae\"]\n",
    "    sol = Solution()\n",
    "    print(sol.findLUSlength(strs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, strs: List[str]) -> int:\n",
    "        def mostcommonstr(str1, str2):\n",
    "            dp = [0] * len(str2)\n",
    "            for i in range(len(str1)):\n",
    "                dp_lst = dp[:]\n",
    "                for j in range(len(str2)):\n",
    "                    if str1[i] == str2[j]:\n",
    "                        dp[j] = (dp_lst[j - 1] if j else 0) + 1\n",
    "                    else:\n",
    "                        dp[j] = max((dp[j - 1] if j else 0), dp_lst[j])\n",
    "                    \n",
    "            return dp[-1]\n",
    "        \n",
    "        res = -1\n",
    "        for i in range(len(strs)):\n",
    "            for j in range(len(strs)):\n",
    "                if j == i:\n",
    "                    continue\n",
    "                com_len = mostcommonstr(strs[i], strs[j])\n",
    "                if com_len == len(strs[i]):\n",
    "                    break\n",
    "            else:\n",
    "                res = max(res, len(strs[i]))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, strs: List[str]) -> int:\n",
    "        def isSub(s,t):\n",
    "            pt_s=pt_t=0\n",
    "            while pt_s<len(s) and pt_t<len(t):\n",
    "                if s[pt_s]==t[pt_t]:\n",
    "                    pt_s+=1\n",
    "                    pt_t+=1\n",
    "                else:\n",
    "                    pt_t+=1\n",
    "            return pt_s==len(s)\n",
    "        \n",
    "        ans=-1\n",
    "        for i,s in enumerate(strs):\n",
    "            check=True\n",
    "            for j,t in enumerate(strs):\n",
    "                if i!=j and isSub(s,t):\n",
    "                    check=False#判断s是不是t的子串\n",
    "                    break\n",
    "            if check:\n",
    "                ans=max(ans,len(s))\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, strs: List[str]) -> int:\n",
    "        def f(s1,s2):\n",
    "            if len(s1)>len(s2):\n",
    "                return False\n",
    "            i=0\n",
    "            j=0\n",
    "            while i<len(s1) and j<len(s2):\n",
    "                if s1[i]==s2[j]:\n",
    "                    i+=1\n",
    "                    j+=1\n",
    "                else:\n",
    "                    j+=1\n",
    "            return i==len(s1)\n",
    "\n",
    "        ans=-1\n",
    "        for i,s in enumerate(strs):\n",
    "            if len(s)>ans and all(not f(s,x) for j,x in enumerate(strs) if j!=i):\n",
    "                ans=len(s)\n",
    "        return ans\n",
    "            \n",
    "        \n",
    "        #最长公共子序列+枚举\n",
    "        # lenth=len(strs)\n",
    "        # def dfs(s1,s2):\n",
    "        #     n=len(s1)\n",
    "        #     m=len(s2)\n",
    "        #     if n>m:\n",
    "        #         return False\n",
    "        #     f=[[0]*(m+1) for _ in range(n+1)]\n",
    "        #     for i in range(n):\n",
    "        #         for j in range(m):\n",
    "        #             if s1[i]==s2[j]:\n",
    "        #                 f[i+1][j+1]=f[i][j]+1\n",
    "        #             else :\n",
    "        #                 f[i+1][j+1]=max(f[i][j+1],f[i+1][j])\n",
    "        #         if f[i+1][j+1]==n:\n",
    "        #             return True\n",
    "        #     return False\n",
    "\n",
    "\n",
    "        # ans=-1\n",
    "        # for i in range(lenth):\n",
    "        #     if len(strs[i])<ans:\n",
    "        #         continue\n",
    "        #     flag=True\n",
    "        #     for j in range(lenth):\n",
    "        #         if j==i:\n",
    "        #             continue \n",
    "        #         if dfs(strs[i],strs[j]):\n",
    "        #             flag=False\n",
    "        #             break\n",
    "        #     if flag:\n",
    "        #         ans=len(strs[i])\n",
    "        # return ans\n",
    "                        \n",
    "                \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, strs: List[str]) -> int:\n",
    "        def is_subseq(s: str, t: str) -> bool:\n",
    "            pt_s = pt_t = 0\n",
    "            while pt_s < len(s) and pt_t < len(t):\n",
    "                if s[pt_s] == t[pt_t]:\n",
    "                    pt_s += 1\n",
    "                pt_t += 1\n",
    "            return pt_s == len(s)\n",
    "        \n",
    "        ans = -1\n",
    "        for i, s in enumerate(strs):\n",
    "            check = True\n",
    "            for j, t in enumerate(strs):\n",
    "                if i != j and is_subseq(s, t):\n",
    "                    check = False\n",
    "                    break\n",
    "            if check:\n",
    "                ans = max(ans, len(s))\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, strs: List[str]) -> int:              \n",
    "     \n",
    "        length = len(strs)\n",
    "        ans = [1000]*length\n",
    "        for i in range(length):\n",
    "            for j in range(length):\n",
    "                if i != j:\n",
    "                    ans1 = 0\n",
    "                    m = len(strs[i])\n",
    "                    n = len(strs[j])\n",
    "                    l = 0\n",
    "                    for k in range(n):\n",
    "                        if l < m and strs[i][l] == strs[j][k]:\n",
    "                            l += 1\n",
    "                    ans1 = -1 if l == m else m\n",
    "                    ans[i] = min(ans[i],ans1)\n",
    "        return max(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, strs: list[str]) -> int:\n",
    "        strs.append('')\n",
    "        def is_part(str1, str2):\n",
    "            i = 0\n",
    "            for c in str1:\n",
    "                if i>=len(str2):\n",
    "                    return False\n",
    "                while c!=str2[i]:\n",
    "                    i+=1\n",
    "                    if i>=len(str2):\n",
    "                        return False\n",
    "                i+=1\n",
    "            return True\n",
    "        strs.sort(key=lambda x:(len(x), x), reverse=True)\n",
    "        for i in range(len(strs)):\n",
    "            if i!=0 and strs[i]==strs[i-1]:\n",
    "                continue\n",
    "            for j in range(len(strs)):\n",
    "                if i!=j:\n",
    "                    if len(strs[i])>len(strs[j]):\n",
    "                        return len(strs[i])\n",
    "                    else:\n",
    "                        if is_part(strs[i], strs[j]):\n",
    "                            break\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, strs: List[str]) -> int:\n",
    "        def isChild(child, father):\n",
    "            if len(child) > len(father):\n",
    "                return False\n",
    "            i = 0\n",
    "            j = 0\n",
    "            while i < len(child) and j < len(father):\n",
    "                if child[i] == father[j]:\n",
    "                    i += 1\n",
    "                    j += 1\n",
    "                else:\n",
    "                    j += 1\n",
    "            if i == len(child):\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "                    \n",
    "        strs = sorted(strs, key = lambda x: len(x), reverse = True)\n",
    "\n",
    "\n",
    "        for i, num_i in enumerate(strs):\n",
    "            for j, num_j in enumerate(strs):\n",
    "                if i != j and isChild(num_i, num_j):\n",
    "                    break \n",
    "            else:\n",
    "                return len(num_i)\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, strs: List[str]) -> int:\n",
    "        max_len = -1\n",
    "        for i, s in enumerate(strs):\n",
    "            is_sub_sequence = False\n",
    "            for j, t in enumerate(strs):\n",
    "                if i == j:\n",
    "                    continue\n",
    "                if self.is_sub_sequence(s, t):\n",
    "                    is_sub_sequence = True\n",
    "                    break\n",
    "            if not is_sub_sequence:\n",
    "                if len(s) > max_len:\n",
    "                    max_len = len(s)\n",
    "                    \n",
    "        return max_len\n",
    "\n",
    "\n",
    "    def is_sub_sequence(self, s, t):\n",
    "        s_id, t_id = 0, 0\n",
    "        while s_id < len(s) and t_id < len(t):\n",
    "            if s[s_id] == t[t_id]:\n",
    "                s_id += 1\n",
    "                t_id += 1\n",
    "            else:\n",
    "                t_id += 1\n",
    "        return s_id == len(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, strs: List[str]) -> int:\n",
    "        n  = len(strs)\n",
    "        def is_squeue(s,p):\n",
    "            i,j=0,0\n",
    "            while i<len(s) and j<len(p):\n",
    "                if s[i]==p[j]:\n",
    "                    i+=1\n",
    "                j+=1\n",
    "            return i == len(s)\n",
    "\n",
    "        ans = -1\n",
    "        for i in range(n):\n",
    "            flag = True\n",
    "            for j in range(n):\n",
    "                if is_squeue(strs[i],strs[j]) and i!=j:\n",
    "                    flag = False\n",
    "                    break \n",
    "            if flag:\n",
    "                ans = max(ans, len(strs[i]))\n",
    "\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, strs: List[str]) -> int:\n",
    "        # 模拟\n",
    "        def is_sub(s1:str, s2:str) -> bool:\n",
    "            if len(s2) < len(s1):\n",
    "                return False\n",
    "            i = 0\n",
    "            j = 0\n",
    "            while i < len(s1) and j < len(s2):\n",
    "                if s1[i] == s2[j]:\n",
    "                    i += 1\n",
    "                    j += 1\n",
    "                else:\n",
    "                    j += 1\n",
    "            return i == len(s1)\n",
    "\n",
    "        \n",
    "        ans = -1\n",
    "        for i, s in enumerate(strs):\n",
    "            if len(s) > ans and all(not is_sub(s, s_) for j, s_ in enumerate(strs) if j != i):\n",
    "                ans = len(s)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, strs: List[str]) -> int:\n",
    "        def is_subseq(s1, s2):\n",
    "            i = 0\n",
    "            j = 0\n",
    "            while i < len(s1) and j < len(s2):\n",
    "                if s1[i] == s2[j]:\n",
    "                    i += 1\n",
    "                    j += 1\n",
    "                else: j += 1\n",
    "            return i == len(s1)\n",
    "\n",
    "        ans = -1\n",
    "        for i, s1 in enumerate(strs):\n",
    "            flag = True\n",
    "            for j, s2 in enumerate(strs):\n",
    "                if i == j: continue\n",
    "                if is_subseq(s1, s2):\n",
    "                    flag = False\n",
    "                    break\n",
    "            if flag: ans = max(ans, len(s1))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, strs: List[str]) -> int:\n",
    "        ans = -1\n",
    "        for i, s1 in enumerate(strs):\n",
    "            flag = True\n",
    "            for j, s2 in enumerate(strs):\n",
    "                if i != j and self.lcs(s1, s2) == len(s1):\n",
    "                    flag = False\n",
    "                    break\n",
    "            if flag:\n",
    "                ans = max(ans, len(s1))\n",
    "        return ans\n",
    "\n",
    "    def lcs(self, text1: str, text2: str) -> int:\n",
    "        f = [0] * (len(text2) + 1)\n",
    "        for x in text1:\n",
    "            pre = 0\n",
    "            for j, y in enumerate(text2):\n",
    "                tmp = f[j + 1]\n",
    "                f[j + 1] = pre + 1 if x == y else max(f[j + 1], f[j])\n",
    "                pre = tmp\n",
    "        return f[-1]\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, strs: List[str]) -> int:\n",
    "        def is_subseq(s: str, t: str) -> bool:\n",
    "            pt_s = pt_t = 0\n",
    "            while pt_s < len(s) and pt_t < len(t):\n",
    "                if s[pt_s] == t[pt_t]:\n",
    "                    pt_s += 1\n",
    "                pt_t += 1\n",
    "            return pt_s == len(s)\n",
    "        \n",
    "        ans = -1\n",
    "        for i, s in enumerate(strs):\n",
    "            check = True\n",
    "            for j, t in enumerate(strs):\n",
    "                if i != j and is_subseq(s, t):\n",
    "                    check = False\n",
    "                    break\n",
    "            if check:\n",
    "                ans = max(ans, len(s))\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, strs: list[str]) -> int:\n",
    "        strs.append('')\n",
    "        def is_part(str1, str2):\n",
    "            i = 0\n",
    "            for c in str1:\n",
    "                if i>=len(str2):\n",
    "                    return False\n",
    "                while c!=str2[i]:\n",
    "                    i+=1\n",
    "                    if i>=len(str2):\n",
    "                        return False\n",
    "                i+=1\n",
    "            return True\n",
    "        strs.sort(key=lambda x:(len(x), x), reverse=True)\n",
    "        for i in range(len(strs)):\n",
    "            if i!=0 and strs[i]==strs[i-1]:\n",
    "                continue\n",
    "            for j in range(len(strs)):\n",
    "                if i!=j:\n",
    "                    if len(strs[i])>len(strs[j]):\n",
    "                        return len(strs[i])\n",
    "                    else:\n",
    "                        if is_part(strs[i], strs[j]):\n",
    "                            break\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, strs: List[str]) -> int:\n",
    "        def is_sub_seq(s1, s2):\n",
    "            i = 0\n",
    "            if len(s1) > len(s2):\n",
    "                return False\n",
    "            for j in range(len(s2)):\n",
    "                if s1[i] == s2[j]:\n",
    "                    i += 1\n",
    "                if i >= len(s1):\n",
    "                    break\n",
    "            if i >= len(s1):\n",
    "                return True\n",
    "            return False\n",
    "\n",
    "        max_len = -1\n",
    "        for i in range(len(strs)):\n",
    "            is_special = True\n",
    "            for j in range(len(strs)):\n",
    "                if i == j:\n",
    "                   continue\n",
    "                if is_sub_seq(strs[i], strs[j]):\n",
    "                    is_special = False\n",
    "                    break\n",
    "            if is_special:\n",
    "                max_len = max(max_len, len(strs[i]))\n",
    "        return max_len\n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, strs: List[str]) -> int:\n",
    "        strs.sort(key=len, reverse=True)\n",
    "        res = -1\n",
    "        def is_sub(a, b):\n",
    "            if len(a) > len(b):\n",
    "                return False\n",
    "            i=j=0\n",
    "            while i < len(a) and j < len(b):\n",
    "                if a[i] == b[j]:\n",
    "                    i+=1\n",
    "                j+=1\n",
    "            return i == len(a)\n",
    "\n",
    "        for i in range(len(strs)):\n",
    "            cal = True\n",
    "            for j in range(len(strs)):\n",
    "                if i != j and is_sub(strs[i], strs[j]):\n",
    "                    cal = False\n",
    "                    break\n",
    "            if cal:\n",
    "                return len(strs[i])\n",
    "  \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, strs: List[str]) -> int:\n",
    "        cnts = collections.Counter(strs)\n",
    "\n",
    "        mp = collections.defaultdict(list)\n",
    "\n",
    "        for ss in strs:\n",
    "            mp[len(ss)].append(ss)\n",
    "\n",
    "        max_ = max(mp.keys())\n",
    "\n",
    "        if len(mp[max_]) == 1:\n",
    "            return max_\n",
    "        else:\n",
    "            for val in mp[max_]:\n",
    "                if cnts[val] == 1:\n",
    "                    return max_\n",
    "        \n",
    "        ls = sorted(mp.keys())\n",
    "\n",
    "        def isSubSequence(a, b):\n",
    "            if len(a) > len(b):\n",
    "                return False\n",
    "            \n",
    "            j = 0\n",
    "\n",
    "            for ele in a:\n",
    "                while j < len(b) and b[j] != ele:\n",
    "                    j += 1\n",
    "                \n",
    "                if j == len(b):\n",
    "                    return False\n",
    "                \n",
    "                j += 1\n",
    "            return True\n",
    "\n",
    "        for i in range(len(ls) - 2, -1, -1):\n",
    "            for val in mp[ls[i]]:\n",
    "                if cnts[val] == 1:\n",
    "                    flag = True\n",
    "                    for k in range(i + 1, len(ls)):\n",
    "                        for parent in mp[ls[k]]:\n",
    "                            if isSubSequence(val, parent):\n",
    "                                flag = False\n",
    "                                break\n",
    "\n",
    "                    if flag:\n",
    "                        return ls[i]\n",
    "\n",
    "\n",
    "        return -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, strs: List[str]) -> int:\n",
    "        res = 0\n",
    "        n = len(strs)\n",
    "        strs.sort(key=lambda x: -len(x))\n",
    "        for i in range(n):\n",
    "            flag = True\n",
    "            for j in range(n):\n",
    "                if i == j:\n",
    "                    continue\n",
    "                if len(strs[i]) > len(strs[j]):\n",
    "                    return len(strs[i])\n",
    "                p = q = 0\n",
    "                while p < len(strs[i]) and q < len(strs[j]):\n",
    "                    if strs[i][p] == strs[j][q]:\n",
    "                        p += 1\n",
    "                    q += 1\n",
    "                if p >= len(strs[i]):\n",
    "                    flag = False\n",
    "                    break\n",
    "            if flag:\n",
    "                return len(strs[i])\n",
    "        return -1\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, strs: List[str]) -> int:\n",
    "        def is_subseq(s: str, t : str) -> bool:\n",
    "            pt_s = pt_t = 0\n",
    "            while pt_s < len(s) and pt_t < len(t):\n",
    "                if s[pt_s] == t[pt_t]:\n",
    "                    pt_s += 1\n",
    "                pt_t += 1\n",
    "            return pt_s == len(s)\n",
    "        ans = -1\n",
    "        for i, s in enumerate(strs):\n",
    "            check = True\n",
    "            for j, t in enumerate(strs):\n",
    "                if i != j and is_subseq(s, t):\n",
    "                    check = False\n",
    "                    break\n",
    "            if check:\n",
    "                ans = max(ans, len(s))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, strs: List[str]) -> int:\n",
    "        def is_sub_str(s1:str,s2:str)->bool:\n",
    "            if len(s2)<len(s1):\n",
    "                return False\n",
    "            i=j=0\n",
    "            while i<len(s1) and j<len(s2):\n",
    "                if s1[i]==s2[j]:\n",
    "                    i+=1\n",
    "                j+=1\n",
    "            return i==len(s1)\n",
    "        \n",
    "        ans=-1\n",
    "        for i,s in enumerate(strs):\n",
    "            if len(s)>ans and all(not is_sub_str(s,s_) for j,s_ in enumerate(strs) if j!=i):\n",
    "                ans=len(s)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, strs: list[str]) -> int:\n",
    "        strs.append('')\n",
    "        @cache\n",
    "        def is_part(str1, str2):\n",
    "            i = 0\n",
    "            for c in str1:\n",
    "                if i>=len(str2):\n",
    "                    return False\n",
    "                while c!=str2[i]:\n",
    "                    i+=1\n",
    "                    if i>=len(str2):\n",
    "                        return False\n",
    "                i+=1\n",
    "            return True\n",
    "        strs.sort(key=lambda x:len(x), reverse=True)\n",
    "        handled = set()\n",
    "        for i in range(len(strs)):\n",
    "            if strs[i] not in handled:\n",
    "                handled.add(strs[i])\n",
    "                for j in range(len(strs)):\n",
    "                    if i!=j:\n",
    "                        if len(strs[i])>len(strs[j]):\n",
    "                            return len(strs[i])\n",
    "                        else:\n",
    "                            if is_part(strs[i], strs[j]):\n",
    "                                break\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, strs: List[str]) -> int:\n",
    "        strs.sort(key = lambda x: -len(x))\n",
    "        def check(s1, s2):\n",
    "            # s1是不是其他的子序列\n",
    "            n_s1, n_s2 = len(s1), len(s2)\n",
    "            i, j = 0, 0\n",
    "            while i < n_s1 and j < n_s2:\n",
    "                if s1[i] == s2[j]:\n",
    "                    i += 1\n",
    "                j += 1\n",
    "            return i == n_s1 # 是子序列\n",
    "\n",
    "        ans = -1\n",
    "        for i, s in enumerate(strs):\n",
    "            n_s = len(s)  # 特殊子序列\n",
    "            flag = True\n",
    "            for j, c in enumerate(strs):\n",
    "\n",
    "                n_c = len(c)\n",
    "\n",
    "                if i != j and n_c >= n_s:\n",
    "\n",
    "                    if check(s,c):\n",
    "                        flag = False\n",
    "                \n",
    "            if flag:\n",
    "                ans = max(ans, n_s)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, strs: List[str]) -> int:\n",
    "        def is_sub(str1,str2):\n",
    "            if len(str1) > len(str2):\n",
    "                return False\n",
    "            i,j = 0,0\n",
    "            while i < len(str1) and j < len(str2):\n",
    "                if str1[i] == str2[j]:\n",
    "                    i+=1\n",
    "                    j+=1\n",
    "                else:\n",
    "                    j+=1\n",
    "            if i == len(str1):\n",
    "                return True\n",
    "            return False\n",
    "        length = -1\n",
    "        for i in range(len(strs)):\n",
    "            flag = 1\n",
    "            for j in range(len(strs)):\n",
    "                if i == j:\n",
    "                    continue\n",
    "                else:\n",
    "                    if is_sub(strs[i],strs[j]):\n",
    "                        flag = 0\n",
    "                        continue\n",
    "            if flag:\n",
    "                length = max(length,len(strs[i]))\n",
    "        return length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def findLUSlength(self, strs: List[str]) -> int:\n",
    "        def is_sub(a, b):\n",
    "            if len(b) > len(a):\n",
    "                return False\n",
    "            j = 0\n",
    "            n = len(b)\n",
    "            for i in range(n):\n",
    "                while j < len(a) and a[j] != b[i]:\n",
    "                    j += 1\n",
    "                if j == len(a):\n",
    "                    return False\n",
    "                j += 1\n",
    "            return True\n",
    "\n",
    "        ans = -1\n",
    "        for k in range(len(strs)):\n",
    "            # search all sub\n",
    "            s = strs[k]\n",
    "            for i in range(len(s)):\n",
    "                for j in range(i+1, len(s)+1):\n",
    "                    seg = s[i:j]\n",
    "                    for p in range(len(strs)):\n",
    "                        if (p != k) and is_sub(strs[p], seg):\n",
    "                            break\n",
    "                    else:\n",
    "                        ans = max(ans, len(seg))\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, strs: List[str]) -> int:\n",
    "        def is_subseq(s: str, t: str) -> bool:\n",
    "            pt_s = pt_t = 0\n",
    "            while pt_s < len(s) and pt_t < len(t):\n",
    "                if s[pt_s] == t[pt_t]:\n",
    "                    pt_s += 1\n",
    "                pt_t += 1\n",
    "            return pt_s == len(s)\n",
    "        ans = -1\n",
    "        for i, s in enumerate(strs):\n",
    "            check = True\n",
    "            for j, t in enumerate(strs):\n",
    "                if i != j and is_subseq(s, t):\n",
    "                    check = False\n",
    "                    break\n",
    "            if check:\n",
    "                ans = max(ans, len(s))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def subseq(s, t):\t# t is subsequence of s\n",
    "\ti = 0\n",
    "\tfor c in s:\n",
    "\t\tif i < len(t) and t[i] == c: i += 1\n",
    "\treturn i == len(t)\n",
    "\n",
    "class Solution:\n",
    "\tdef findLUSlength(self, strs):\n",
    "\t\tstrs.sort(key=len, reverse=True)\n",
    "\t\tfor i, t in enumerate(strs):\n",
    "\t\t\tif all(not subseq(s, t) for j, s in enumerate(strs) if i != j):\n",
    "\t\t\t\treturn len(t)\n",
    "\t\treturn -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, strs: List[str]) -> int:\n",
    "        def is_sub_str(s1:str,s2:str)->bool:\n",
    "            if len(s2)<len(s1):\n",
    "                return False\n",
    "            i=j=0\n",
    "            while i<len(s1) and j<len(s2):\n",
    "                if s1[i]==s2[j]:\n",
    "                    i+=1\n",
    "                    j+=1\n",
    "                else:\n",
    "                    j+=1\n",
    "            return i==len(s1)\n",
    "\n",
    "        ans=-1\n",
    "        for i,s in enumerate(strs):\n",
    "            if len(s)>ans and all(not is_sub_str(s,s_) for j,s_ in enumerate(strs) if j!=i):\n",
    "                ans=len(s)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, strs: List[str]) -> int:\n",
    "        def is_subseq(s: str, t: str) -> bool:\n",
    "            pt_s, pt_t = 0, 0\n",
    "            while pt_s < len(s) and pt_t < len(t):\n",
    "                if s[pt_s] == t[pt_t]:\n",
    "                    pt_s += 1\n",
    "                pt_t += 1\n",
    "            return pt_s == len(s)\n",
    "        n = len(strs)\n",
    "        ans = -1\n",
    "        for i in range(n):\n",
    "            flag = True\n",
    "            for j in range(n):\n",
    "                if i != j and is_subseq(strs[i],strs[j]):\n",
    "                    flag = False\n",
    "                    break\n",
    "            if flag:\n",
    "                ans = max(ans,len(strs[i]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, strs: List[str]) -> int:\n",
    "        max_len = -1\n",
    "        for i, s in enumerate(strs):\n",
    "            is_sub_sequence = False\n",
    "            for j, t in enumerate(strs):\n",
    "                if i == j:\n",
    "                    continue\n",
    "                if self.is_sub_sequence(s, t):\n",
    "                    is_sub_sequence = True\n",
    "                    break\n",
    "            if not is_sub_sequence:\n",
    "                if len(s) > max_len:\n",
    "                    max_len = len(s)\n",
    "                    \n",
    "        return max_len\n",
    "\n",
    "\n",
    "    def is_sub_sequence(self, s, t):\n",
    "        s_id, t_id = 0, 0\n",
    "        while s_id < len(s) and t_id < len(t):\n",
    "            if s[s_id] == t[t_id]:\n",
    "                s_id += 1\n",
    "                t_id += 1\n",
    "            else:\n",
    "                t_id += 1\n",
    "        return s_id == len(s)\n",
    "\n",
    "\n",
    "\"\"\"\n",
    "1. 定义好判断是否子序列函数后, 直接遍历strs, 看某个str是否是其他str的子序列, 如果是, 则不是答案要求的\"特殊序列\"\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, strs: List[str]) -> int:\n",
    "        def is_sub_str(s1:str , s2:str) -> bool:\n",
    "            if len(s2) < len(s1):\n",
    "                return False\n",
    "            i = j = 0\n",
    "            while i < len(s1) and j < len(s2):\n",
    "                if s1[i] == s2[j]:\n",
    "                    i += 1\n",
    "                    j += 1\n",
    "                else:\n",
    "                    j += 1\n",
    "            return i == len(s1)\n",
    "            \n",
    "        ans = -1\n",
    "        for i, s in enumerate(strs):\n",
    "            if len(s) > ans and all(not is_sub_str(s, s_) for j, s_ in enumerate(strs) if j != i):\n",
    "                ans = len(s)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, strs: List[str]) -> int:\n",
    "        dob=set()\n",
    "        s=set()\n",
    "        for i in strs:\n",
    "            if i not in s:\n",
    "                s.add(i)\n",
    "            else:\n",
    "                dob.add(i)\n",
    "        for i in dob:\n",
    "            s.remove(i)\n",
    "        def ifsub(a,b):\n",
    "            i,j=0,0\n",
    "            while i<len(a) and j<len(b):\n",
    "                if a[i]==b[j]:\n",
    "                    i+=1\n",
    "                j+=1\n",
    "            return i==len(a)\n",
    "        def chack(i):\n",
    "            for j in dob:\n",
    "                if ifsub(i,j):\n",
    "                    return False\n",
    "            return True\n",
    "        s=sorted(list(s),key=lambda x:len(x),reverse=True)\n",
    "        for i in s:\n",
    "            if chack(i):\n",
    "                return len(i)\n",
    "        return -1\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, strs: List[str]) -> int:\n",
    "        res = 0\n",
    "        n = len(strs)\n",
    "        strs.sort(key=lambda x: -len(x))\n",
    "        for i in range(n):\n",
    "            flag = True\n",
    "            for j in range(n):\n",
    "                if i == j:\n",
    "                    continue\n",
    "                if len(strs[i]) > len(strs[j]):\n",
    "                    break\n",
    "                p = q = 0\n",
    "                while p < len(strs[i]) and q < len(strs[j]):\n",
    "                    if strs[i][p] == strs[j][q]:\n",
    "                        p += 1\n",
    "                    q += 1\n",
    "                if p >= len(strs[i]):\n",
    "                    flag = False\n",
    "                    break\n",
    "            if flag:\n",
    "                return len(strs[i])\n",
    "        return -1\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, strs: List[str]) -> int:\n",
    "        strs.sort(key = lambda x: -len(x))\n",
    "        def check(s1, s2):\n",
    "            # s1是不是其他的子序列\n",
    "            n_s1, n_s2 = len(s1), len(s2)\n",
    "            i, j = 0, 0\n",
    "            while i < n_s1 and j < n_s2:\n",
    "                if s1[i] == s2[j]:\n",
    "                    i += 1\n",
    "                j += 1\n",
    "            return i == n_s1 # 是子序列\n",
    "\n",
    "        ans = -1\n",
    "        for i, s in enumerate(strs):\n",
    "            n_s = len(s)  # 特殊子序列\n",
    "            flag = True\n",
    "            for j, c in enumerate(strs):\n",
    "\n",
    "                n_c = len(c)\n",
    "\n",
    "                if i != j and n_c >= n_s:\n",
    "\n",
    "                    if check(s,c):\n",
    "                        flag = False\n",
    "                \n",
    "            if flag:\n",
    "                ans = max(ans, n_s)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, strs: List[str]) -> int:\n",
    "        def is_subseq(s: str, t: str) -> bool:\n",
    "            pt_s = pt_t = 0\n",
    "            while pt_s < len(s) and pt_t < len(t):\n",
    "                if s[pt_s] == t[pt_t]:\n",
    "                    pt_s += 1\n",
    "                pt_t += 1\n",
    "            return pt_s == len(s)\n",
    "        \n",
    "        ans = -1\n",
    "        for i, s in enumerate(strs):\n",
    "            check = True\n",
    "            for j, t in enumerate(strs):\n",
    "                if i != j and is_subseq(s, t):\n",
    "                    check = False\n",
    "                    break\n",
    "            if check:\n",
    "                ans = max(ans, len(s))\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def findLUSlength(self, strs):\n",
    "        \"\"\"\n",
    "        :type strs: List[str]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        def is_sub(a,b):\n",
    "            la,lb = len(a), len(b)\n",
    "            if la > lb:\n",
    "                return False\n",
    "            l = 0\n",
    "            for c in b:\n",
    "                if a[l] == c:\n",
    "                    l += 1\n",
    "                if l == la:\n",
    "                    return True\n",
    "            return False\n",
    "        \n",
    "        n = len(strs)\n",
    "        ans = -1\n",
    "        for i in range(n):\n",
    "            if len(strs[i]) <= ans:\n",
    "                continue\n",
    "            ok = True\n",
    "            for j in range(n):\n",
    "                if i == j:\n",
    "                    continue\n",
    "                if not ok:\n",
    "                    break\n",
    "                if is_sub(strs[i],strs[j]):\n",
    "                    ok = False\n",
    "            if ok:\n",
    "                ans = len(strs[i])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, strs: List[str]) -> int:\n",
    "        # 模拟\n",
    "        # def is_sub(s1:str, s2:str) -> bool:\n",
    "        #     if len(s2) < len(s1):\n",
    "        #         return False\n",
    "        #     i = 0\n",
    "        #     j = 0\n",
    "        #     while i < len(s1) and j < len(s2):\n",
    "        #         if s1[i] == s2[j]:\n",
    "        #             i += 1\n",
    "        #             j += 1\n",
    "        #         else:\n",
    "        #             j += 1\n",
    "        #     return i == len(s1)\n",
    "\n",
    "        \n",
    "        # ans = -1\n",
    "        # for i, s in enumerate(strs):\n",
    "        #     print(i, s)\n",
    "        #     if len(s) > ans and all(not is_sub(s, s_) for j, s_ in enumerate(strs) if j != i):\n",
    "        #         ans = len(s)\n",
    "        # return ans\n",
    "\n",
    "\n",
    "\n",
    "        # 思路一样的\n",
    "        def check(s, t):\n",
    "            if len(t) < m:\n",
    "                return True\n",
    "            k = 0 \n",
    "            for w in t:\n",
    "                if k < m and w == s[k]:\n",
    "                    k += 1\n",
    "                    if k == m:\n",
    "                        return False\n",
    "            return True\n",
    "        strs.sort(key=lambda x: -len(x))\n",
    "        n = len(strs)\n",
    "        for i in range(n):\n",
    "            m = len(strs[i])\n",
    "            if all(check(strs[i], strs[j]) for j in range(n) if j != i):\n",
    "                return m\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, strs: List[str]) -> int:\n",
    "        def is_substr(curr: str, other: str) -> bool:\n",
    "            pt_curr, pt_other = 0, 0\n",
    "            while pt_curr < len(curr) and pt_other < len(other):\n",
    "                if curr[pt_curr] == other[pt_other]:\n",
    "                    pt_curr += 1\n",
    "                pt_other += 1\n",
    "            return pt_curr == len(curr)\n",
    "\n",
    "        ans = -1\n",
    "        for i, curr in enumerate(strs):\n",
    "            flag = True\n",
    "            for j, other in enumerate(strs):\n",
    "                if i != j and is_substr(curr, other):\n",
    "                    flag = False\n",
    "                    break\n",
    "            if flag:\n",
    "                ans = max(ans, len(curr))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, strs: List[str]) -> int:\n",
    "        res = 0\n",
    "        n = len(strs)\n",
    "        strs.sort(key=lambda x: -len(x))\n",
    "        for i in range(n):\n",
    "            flag = True\n",
    "            for j in range(n):\n",
    "                if i == j:\n",
    "                    continue\n",
    "                if len(strs[i]) > len(strs[j]):\n",
    "                    break\n",
    "                p = q = 0\n",
    "                while p < len(strs[i]) and q < len(strs[j]):\n",
    "                    if strs[i][p] == strs[j][q]:\n",
    "                        p += 1\n",
    "                    q += 1\n",
    "                if p >= len(strs[i]):\n",
    "                    flag = False\n",
    "                    break\n",
    "            if flag:\n",
    "                return len(strs[i])\n",
    "        return -1\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, strs: List[str]) -> int:\n",
    "        res = -1\n",
    "        n = len(strs)\n",
    "        # strs.sort(key=lambda x: -len(x))\n",
    "        for i in range(n):\n",
    "            flag = True\n",
    "            for j in range(n):\n",
    "                if i == j:\n",
    "                    continue\n",
    "                if len(strs[i]) > len(strs[j]):\n",
    "                    continue\n",
    "                p = q = 0\n",
    "                while p < len(strs[i]) and q < len(strs[j]):\n",
    "                    if strs[i][p] == strs[j][q]:\n",
    "                        p += 1\n",
    "                    q += 1\n",
    "                if p >= len(strs[i]):\n",
    "                    flag = False\n",
    "                    break\n",
    "            if flag:\n",
    "                res = max(res, len(strs[i]))\n",
    "        return res\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, strs):\n",
    "        def is_subsequence(s, t):\n",
    "            t = iter(t)\n",
    "            return all(i in t for i in s)\n",
    "\n",
    "        strs.sort(key=len, reverse=True)\n",
    "        for i, word in enumerate(strs):\n",
    "            if all(not is_subsequence(word, strs[j]) for j in range(len(strs)) if j != i):\n",
    "                return len(word)\n",
    "\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, strs: List[str]) -> int:\n",
    "        d = defaultdict(list)\n",
    "        for s in strs:\n",
    "            d[len(s)].append(s)\n",
    "        L = sorted(d.keys(), reverse=True)\n",
    "        cnt = Counter(strs)\n",
    "        str_set = set(strs)\n",
    "\n",
    "        def f(x, y):  # 验证y是不是x的子序列\n",
    "            if len(x) < len(y):\n",
    "                return False\n",
    "            elif len(x) == len(y):\n",
    "                return x == y\n",
    "            else:\n",
    "                left = 0\n",
    "                for right in range(len(y)):\n",
    "                    while left < len(x) and x[left] != y[right]:\n",
    "                        left += 1\n",
    "                    if left == len(x):\n",
    "                        return False\n",
    "                    left += 1\n",
    "                return True\n",
    "\n",
    "        for k in L:\n",
    "            for ss in d[k]:\n",
    "                if cnt[ss] > 1:\n",
    "                    continue\n",
    "                res = 0\n",
    "                for j in str_set:\n",
    "                    if f(j, ss):\n",
    "                        res += 1\n",
    "                if res == 1:\n",
    "                    return k\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 枚举\n",
    "class Solution:\n",
    "    def findLUSlength(self, strs: List[str]) -> int:\n",
    "        strs.sort(key=lambda s:len(s),reverse=True)\n",
    "        pre=\"\"\n",
    "        ans=-1\n",
    "        for i in range(len(strs)): # 作为待匹配子序列\n",
    "            if strs[i]==pre:\n",
    "                continue\n",
    "            success=True\n",
    "            for j in range(0,len(strs)): # 较长的字符串\n",
    "                if i==j: continue\n",
    "                m,n=len(strs[j]),len(strs[i])\n",
    "                if n>m: break\n",
    "                s,t=0,0\n",
    "                while s<n and t<m:\n",
    "                    if strs[i][s]==strs[j][t]:\n",
    "                        s+=1\n",
    "                    t+=1\n",
    "                if s==n:\n",
    "                    success=False\n",
    "            if success:\n",
    "                ans=len(strs[i])\n",
    "                break\n",
    "            pre=s\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, strs: List[str]) -> int:\n",
    "        c = Counter(strs)\n",
    "        if len(c) == 1:\n",
    "            return -1\n",
    "        strs = list(c.keys())\n",
    "        strs.sort(key=lambda x:(len(x), x), reverse=True)\n",
    "        len_k = len(strs)\n",
    "        visited = [0] * len_k\n",
    "        for i, key in enumerate(strs):\n",
    "            if c[key] > 1:\n",
    "                visited[i] = 2\n",
    "        i = 0\n",
    "        while i < len_k:\n",
    "            if visited[i] == 1:\n",
    "                i += 1\n",
    "                continue\n",
    "            a = strs[i]\n",
    "            len_a = len(a)\n",
    "            for j in range(i + 1, len_k):\n",
    "                if len_a > len(strs[j]) and visited[i] == 0:\n",
    "                    return len_a\n",
    "                i_a = 0\n",
    "                for c_b in strs[j]:\n",
    "                    while i_a < len_a and c_b != a[i_a]:\n",
    "                        i_a += 1\n",
    "                    if i_a == len_a:\n",
    "                        if visited[i] == 0:\n",
    "                            return len_a\n",
    "                        else:\n",
    "                            i_a += 1\n",
    "                            break\n",
    "                    i_a += 1\n",
    "                if i_a <= len_a:\n",
    "                    visited[j] = 1\n",
    "            i += 1\n",
    "        return -1 if visited[-1] else len(strs[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, strs: List[str]) -> int:\n",
    "        def is_subseq(s1, s2):\n",
    "            i, j = 0, 0\n",
    "            while i < len(s1) and j < len(s2):\n",
    "                if s1[i] == s2[j]:\n",
    "                    i += 1\n",
    "                j += 1\n",
    "            \n",
    "            return i == len(s1)\n",
    "        res = -1\n",
    "        for i, s in enumerate(strs):\n",
    "            is_special = True\n",
    "            for j, t in enumerate(strs):\n",
    "                if i != j and is_subseq(s, t):\n",
    "                    is_special = False\n",
    "                    break\n",
    "            if is_special:\n",
    "                res = max(res, len(s))\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, strs: List[str]) -> int:\n",
    "        res = -1\n",
    "        n = len(strs)\n",
    "        # strs.sort(key=lambda x: -len(x))\n",
    "        for i in range(n):\n",
    "            flag = True\n",
    "            for j in range(n):\n",
    "                if i == j:\n",
    "                    continue\n",
    "                if len(strs[i]) > len(strs[j]):\n",
    "                    continue\n",
    "                p = q = 0\n",
    "                while p < len(strs[i]) and q < len(strs[j]):\n",
    "                    if strs[i][p] == strs[j][q]:\n",
    "                        p += 1\n",
    "                    q += 1\n",
    "                if p >= len(strs[i]):\n",
    "                    flag = False\n",
    "                    break\n",
    "            if flag:\n",
    "                res = max(res, len(strs[i]))\n",
    "        return res\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, strs: List[str]) -> int:\n",
    "        def subStr(s, t):\n",
    "            i, j = 0, 0\n",
    "            while i<len(s) and j<len(t):\n",
    "                if s[i] == t[j]:\n",
    "                    i += 1\n",
    "                j += 1\n",
    "            if i==len(s):\n",
    "                return True\n",
    "            return False\n",
    "        res = -1\n",
    "        for i, s in enumerate(strs):\n",
    "            check = True\n",
    "            for j, t in enumerate(strs):\n",
    "                if i!=j and subStr(s, t):\n",
    "                    check=False\n",
    "                    break\n",
    "            if check:\n",
    "                res = max(res, len(s))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, strs: List[str]) -> int:\n",
    "        def is_subseq(s: str, t: str) -> bool:\n",
    "            pt_s = pt_t = 0\n",
    "            while pt_s < len(s) and pt_t < len(t):\n",
    "                if s[pt_s] == t[pt_t]:\n",
    "                    pt_s += 1\n",
    "                pt_t += 1\n",
    "            return pt_s == len(s)\n",
    "        \n",
    "        ans = -1\n",
    "        for i, s in enumerate(strs):\n",
    "            check = True\n",
    "            for j, t in enumerate(strs):\n",
    "                if i != j and is_subseq(s, t):\n",
    "                    check = False\n",
    "                    break\n",
    "            if check:\n",
    "                ans = max(ans, len(s))\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, s: List[str]) -> int:\n",
    "        def f(a,b):  #a不是b的子序列？\n",
    "            a=list(a)\n",
    "            b=list(b)\n",
    "            while a and b:\n",
    "                if a[-1]==b[-1]:\n",
    "                    a.pop()\n",
    "                    b.pop()\n",
    "                else:\n",
    "                    b.pop()\n",
    "            return len(a)>0\n",
    "        n=len(s)\n",
    "        res=-1\n",
    "        for i in range(n):\n",
    "            if all(f(s[i],s[j]) for j in range(n) if i!=j):\n",
    "                res=max(res,len(s[i]))\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, strs: List[str]) -> int:\n",
    "        ans = -1\n",
    "        for i, word in enumerate(strs):\n",
    "            for j in range(len(strs)):\n",
    "                if j == i:\n",
    "                    continue\n",
    "                if self.isSubsequ(word,strs[j]):\n",
    "                    break\n",
    "            else:\n",
    "                ans = max(ans, len(word))\n",
    "        return ans\n",
    "                \n",
    "\n",
    "    def isSubsequ(self, child, mother):\n",
    "        if len(child) > len(mother):\n",
    "            return False\n",
    "        else:\n",
    "            i, j = 0, 0\n",
    "        while i < len(child) and j < len(mother):\n",
    "            if child[i] == mother[j]:\n",
    "                i += 1\n",
    "            j += 1\n",
    "        if i >= len(child):\n",
    "            return True\n",
    "        elif i < len(child):\n",
    "            return False\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @staticmethod\n",
    "    def subseq(string,long_string)->bool:\n",
    "        l,r=0,0\n",
    "        while l<len(string) and r<len(long_string):\n",
    "            if(string[l]==long_string[r]):\n",
    "                l+=1\n",
    "                r+=1\n",
    "            else:\n",
    "                r+=1\n",
    "        return l==len(string)\n",
    "        \n",
    "    def findLUSlength(self, strs: List[str]) -> int:\n",
    "        frequent={}\n",
    "        for string in strs:\n",
    "            if string not in frequent:\n",
    "                frequent[string]=1\n",
    "            else:\n",
    "                frequent[string]+=1\n",
    "        dup_lst=[]\n",
    "        candidate_lst=[]\n",
    "        for string,freq in frequent.items():\n",
    "            if(freq==1):\n",
    "                candidate_lst.append(string)\n",
    "            else:\n",
    "                dup_lst.append(string)\n",
    "        candidate_lst.sort(key=lambda x:len(x),reverse=True)\n",
    "        print(candidate_lst)\n",
    "        for string in candidate_lst:\n",
    "            substr=False\n",
    "            for long_string in dup_lst:\n",
    "                if len(string)<len(long_string) and self.subseq(string,long_string):\n",
    "                    substr=True\n",
    "                    break\n",
    "            if substr==False:\n",
    "                return len(string)\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "          \n",
    "    def findLUSlength(self, strs: List[str]) -> int:\n",
    "        def pp(text1: str, text2: str) -> int:     \n",
    "          @cache \n",
    "          def g(i,j):\n",
    "            if i<0 or j<0:\n",
    "                return 0\n",
    "            res =0\n",
    "            if text1[i]==text2[j]:\n",
    "                 res=g(i-1,j-1)+1   \n",
    "            return max(g(i-1,j),res,g(i,j-1))\n",
    "          return g(len(text1)-1,len(text2)-1)  \n",
    "\n",
    "        mx=0\n",
    "        for i in range(len(strs)):\n",
    "            if len(strs[i])<mx:\n",
    "                continue\n",
    "            a=True    \n",
    "            for j in range(len(strs)):\n",
    "               if i==j:\n",
    "                   continue\n",
    "               f=pp(strs[i],strs[j])\n",
    "               if f==len(strs[i]):\n",
    "                   a=False\n",
    "            if a:\n",
    "             mx=len(strs[i])\n",
    "        return  mx if mx!=0 else -1          "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, strs: List[str]) -> int:\n",
    "        '''\n",
    "        由于每个单词的长度都很小, 又要遍历其中的子序列, 所以用mask来表示单词中哪些字符在子序列中\n",
    "        f[mask][j]表示当子序列的选择是mask的时候, 最后一个字符在strs[j]中出现的位置\n",
    "        由于mask == 0表示没有选择, 因此f[mask][*] == -1.使用-2来代表无效\n",
    "        '''\n",
    "        N = len(strs)\n",
    "        ans = 0\n",
    "        for i in range(N):\n",
    "            word = strs[i]\n",
    "            n = len(word)\n",
    "            f = [[-2] * N for _ in range(1 << n)]\n",
    "            f[0] = [-1] * N\n",
    "            for mask in range(1<<n):\n",
    "                for j in range(N):\n",
    "                    word2 = strs[j]\n",
    "                    '''\n",
    "                    该子序列不是strs[j]的子序列\n",
    "                    '''\n",
    "                    if f[mask][j] == -2: continue\n",
    "                    s = f[mask][j]\n",
    "                    \n",
    "                    # 对于一个子序列, 它后面可以选择任意的字符一起组成新的子序列\n",
    "                    for kk in range(mask.bit_length(), n):\n",
    "                        c = word[kk] # 下一个可以添加的字符\n",
    "                        '''\n",
    "                        寻找下一个添加的字符在strs[j]中最小的位置\n",
    "                        '''\n",
    "                        for ss in range(s+1, len(word2)):\n",
    "                            if word2[ss] == c:\n",
    "                                # 新的状态\n",
    "                                f[mask | (1<<kk)][j] = ss\n",
    "                                break\n",
    "\n",
    "            for mask in range(1, 1<<n):\n",
    "                cnt = 0\n",
    "                for j in range(N):\n",
    "                    if f[mask][j] != -2:\n",
    "                        cnt += 1\n",
    "                \n",
    "                # 该子序列只能是一个字符串(就是他自己所在的字符串)的子序列\n",
    "                if cnt == 1:\n",
    "                    ans = max(ans, mask.bit_count())\n",
    "        \n",
    "        return ans if ans > 0 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, strs: List[str]) -> int:\n",
    "        N = len(strs)\n",
    "        ans = 0\n",
    "        for i in range(N):\n",
    "            word = strs[i]\n",
    "            n = len(word)\n",
    "            f = [[-2] * N for _ in range(1 << n)]\n",
    "            f[0] = [-1] * N\n",
    "            for mask in range(1<<n):\n",
    "                for j in range(N):\n",
    "                    word2 = strs[j]\n",
    "                    if f[mask][j] == -2: continue\n",
    "                    s = f[mask][j]\n",
    "                    for kk in range(mask.bit_length(), n):\n",
    "                        c = word[kk] # 下一个可以添加的字符\n",
    "                        for ss in range(s+1, len(word2)):\n",
    "                            if word2[ss] == c:\n",
    "                                f[mask | (1<<kk)][j] = ss\n",
    "                                break\n",
    "\n",
    "            for mask in range(1, 1<<n):\n",
    "                cnt = 0\n",
    "                for j in range(N):\n",
    "                    if f[mask][j] != -2:\n",
    "                        cnt += 1\n",
    "                if cnt == 1:\n",
    "                    ans = max(ans, mask.bit_count())\n",
    "        \n",
    "        return ans if ans > 0 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def f(self, s1: str, s2: str) -> bool:\n",
    "        p = 0\n",
    "        for i in s2:\n",
    "            if s1[p] == i: p+=1\n",
    "            if p == len(s1): return True\n",
    "        return False\n",
    "\n",
    "    def findLUSlength(self, strs: List[str]) -> int:\n",
    "        res, myset = -1, set() \n",
    "        for s in strs:\n",
    "            for x in itertools.product([0, 1], repeat=len(s)):\n",
    "                s1 = ''.join([i for i, j in zip(s, x) if j==1])\n",
    "                if s1 and s1 not in myset and len(s1)>res:\n",
    "                    if sum(self.f(s1, s2) for s2 in strs)==1: res = len(s1)\n",
    "                    myset.add(s1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, strs: List[str]) -> int:\n",
    "        mydict=Counter()\n",
    "        def dfs(k,word):\n",
    "            if k==len(word):\n",
    "                nonlocal mydict\n",
    "                ret=\"\"\n",
    "                for i in range(len(word)):\n",
    "                    if pre[i]==1:\n",
    "                        ret+=word[i]\n",
    "                mydict[ret]+=1\n",
    "                return \n",
    "            pre[k]=1\n",
    "            dfs(k+1,word)\n",
    "            pre[k]=0\n",
    "            dfs(k+1,word)\n",
    "        for item in strs:\n",
    "            pre=[0]*10\n",
    "            dfs(0,item)\n",
    "        ret=-1\n",
    "        for key,val in mydict.items():\n",
    "            if val==1:\n",
    "                ret=max(len(key),ret)\n",
    "        # print(mydict)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, strs: List[str]) -> int:\n",
    "        substr = collections.defaultdict(set)\n",
    "        for i in range(len(strs)):\n",
    "            for j in range(1, 1 << len(strs[i])):\n",
    "                temp = []\n",
    "                k = 0\n",
    "                while j >> k:\n",
    "                    if (j >> k) & 1:   temp.append(strs[i][k])\n",
    "                    k += 1\n",
    "                substr[\"\".join(temp)].add(i)\n",
    "        ans = -1\n",
    "        for word in strs:\n",
    "            if len(substr[word]) == 1: ans = max(ans, len(word))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, strs: List[str]) -> int:\n",
    "        substr = collections.defaultdict(set)\n",
    "        for i in range(len(strs)):\n",
    "            for j in range(1, 1 << len(strs[i])):\n",
    "                temp = []\n",
    "                k = 0\n",
    "                while j >> k:\n",
    "                    if (j >> k) & 1:   temp.append(strs[i][k])\n",
    "                    k += 1\n",
    "                substr[\"\".join(temp)].add(i)\n",
    "        ans = -1\n",
    "        for key, value in substr.items():\n",
    "            if len(value) == 1: ans = max(ans, len(key))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLUSlength(self, strs: List[str]) -> int:\n",
    "        substr = collections.defaultdict(set)\n",
    "        for i in range(len(strs)):\n",
    "            for j in range(1, 1 << len(strs[i])):\n",
    "                temp = []\n",
    "                k = 0\n",
    "                while j >> k:\n",
    "                    if (j >> k) & 1:   temp.append(strs[i][k])\n",
    "                    k += 1\n",
    "                substr[\"\".join(temp)].add(i)\n",
    "        ans = -1\n",
    "        for word in strs:\n",
    "            if len(substr[word]) == 1: ans = max(ans, len(word))\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
